package com.yvon.service.demo.algorithm.offer;

/**
 * 找出数组中重复的数字。
 *
 * 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
 * https://doocs.gitee.io/leetcode/#/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9803.%20%E6%95%B0%E7%BB%84%E4%B8%AD%E9%87%8D%E5%A4%8D%E7%9A%84%E6%95%B0%E5%AD%97/README
 */
public class P03 {

    public static void main(String[] args) {
        Solution solution = new P03().new Solution();
        int[] nums = new int[]{2, 3, 4, 3, 5 ,9 ,8, 3, 9, 8};
        System.out.println(solution.findRepeatNumber(nums));
    }


    /**
     * 原地交换
     * 0 ～ n-1 范围内的数，分别还原到对应的位置上，如：数字 2 交换到下标为 2 的位置。若交换过程中发现重复，则直接返回。
     */
    class Solution {
        public int findRepeatNumber(int[] nums) {
            for (int i = 0; i < nums.length; i++) {
                while (nums[i] != i) {
                    if (nums[i] == nums[nums[i]]) {
                        return nums[i];
                    }
                    swap(nums, i, nums[i]);
                }
            }
            return -1;
        }

        private void swap(int[] nums, int i, int j) {
            int t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
    }
}

